package offerv1;

public class Offer13 {
    int result = 0;

    public int movingCount1(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        helper(visited, m, n, k, 0, 0);
        return result;
    }

    private void helper(boolean[][] visited, int m, int n, int k, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }

        if (visited[i][j]) {
            return;
        }

        if ((i / 10 + i % 10 + j / 10 + j % 10) > k) {
            return;
        }

        visited[i][j] = true;
        result++;
        helper(visited, m, n, k, i + 1, j);
        helper(visited, m, n, k, i - 1, j);
        helper(visited, m, n, k, i, j + 1);
        helper(visited, m, n, k, i, j - 1);
    }

    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }

        boolean[][] vis = new boolean[m][n];
        int ans = 1;
        vis[0][0] = true;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 && j == 0) || (i / 10 + i % 10 + j / 10 + j % 10) > k) {
                    continue;
                }
                // 边界判断
                if (i - 1 >= 0) {
                    vis[i][j] |= vis[i - 1][j];
                }

                if (j - 1 >= 0) {
                    vis[i][j] |= vis[i][j - 1];
                }

                if (!vis[i][j]) {
                    break;
                }

                ans += 1;
            }
        }
        return ans;
    }
}
